rtk 2008

2008.1.1

GrbaveBesede

1. podnaloga

Nekateri spletni wiki strežniki omogočajo skrajšan zapis sklicev na druge dokumente tako, da v besedilu prepoznajo grbave besede (angleško: CamelCase) in jih obravnavajo posebej. Grbava beseda je sestavljena iz velikih in malih črk, pri tem se mora v njej vsaj dvakrat pojaviti par velike in male črke (v tem vrstnem redu).

Primeri grbavih besed:

• DomaNaKrimu
• WriteLn
• skokNaKonec
• NaCl
• NotredamskiZvonar

Primeri besed, ki niso grbave:

• dom
• naKrimu
• Grbavebesede
• Write
• NaOH

Naloga

Napisali smo program, ki prebere besedilo iz vhodne datoteke (bere naj do konca) in v njem poišče vse grbave besede ter jih izpiše, vsako v svojo vrstico. Besede v vhodni datoteki so ločene med seboj s presledki ali konci vrstic; predpostavili smo, da številk in posebnih znakov v besedilu ni.

Vrstice programa pa so se premešale. Uredi jih, da bo program zopet deloval.

with open(datoteka, 'r') as txt:
import re
        for beseda in re.findall("[a-z]*[A-Z]+[a-z]+[A-Z]+[a-z]+[A-Za-z]*", vrstica):
            print(beseda)
datoteka = input('')
    for vrstica in txt:

Vhodni podatki

Datoteka .txt.

Izhodni podatki

Izpis grbavih besed na zaslon. Vsaka grbava beseda naj bo napisana v svoji vrstici.

Uradna rešitev

import re
datoteka = input('')
with open(datoteka, 'r') as txt:
    for vrstica in txt:
        for beseda in re.findall("[a-z]*[A-Z]+[a-z]+[A-Z]+[a-z]+[A-Za-z]*", vrstica):
            print(beseda)

2008.1.2

Predavalnice

1. podnaloga

Na neki srednji šoli prirejajo večji dogodek. Potekal bo ves dan in bo obsegal kopico predavanj. Vsako predavanje ima znan čas začetka in konca ter zasede eno predavalnico. Nekatera predavanja potekajo hkrati, zato je seveda potrebnih več učilnic. Časi predavanj so določeni tako, da je v čas posameznega predavanja že zajet tudi čas, ki je potreben za to, da se na koncu predavanja predavalnica izprazni in da lahko vanjo pridejo poslušalci naslednjega predavanja. Torej, če imamo podatek, da se neko predavanje začne ob istem času, ob katerem se neko drugo predavanje konča, to pomeni, da lahko tidve predavanji uporabljata isto predavanico. Pomagaj ravnatelju napisati program, ki bo izračunal največje število hkratnih predavanj, da bo znal priskrbeti potrebno število predavalnic.

Naloga

Ravnatelj pozna čas (ure in minute) začetka in konca vsakega dogodka. Vrstice funkcije, ki prebere te podatke iz vhodne datoteke in izpiše potrebno število predavalnic, so se premešale. Uredi jih, da bo funkcija delovala.

    while minute_konca > minute_zacetka:
    predavalnice_po_minutah[minute_zacetka] += 1
    """Izračuna število predavalnic, ki jih potrebujemo. Vhodni podatek je datoteka,
    v kateri je v vsaki vrstici napisano predavanje, čas začetka in konca predavanja.
    Podatki v vrstici so ločeni z vejico."""
    def stevilo_predavalnic(datoteka):
    return max(predavalnice_po_minutah)
    predavalnice_po_minutah = 1440 * [0]
    # V dnevu je 1440 minut. Vsaka celica pove, koliko predavanj poteka v neki minuti.
    zacetek = re.findall(", (\d\d):(\d\d), \d\d:\d\d", predavanje)[0]
    minute_zacetka = int(zacetek[0]) * 60 + int(zacetek[1])
    minute_konca = int(konec[0]) * 60 + int(konec[1])
    minute_zacetka += 1
    for predavanje in predavanja:
    with open(datoteka, 'r') as predavanja:
    konec = re.findall("\d\d:\d\d, (\d\d):(\d\d)", predavanje)[0]

Vhodni podatki

Datoteka, v kateri je v vsaki vrstici napisan dogodek, nato vejica s presledkom in čas začetka ter vejica s presledkom in čas konca predavanja. Ure in minute so ločene z dvopičjem.

Primeri vhodnih podatkov

Jean-Sébastien Caux: Quench, Hydro and Floquet Dynamics in Integrable Systems, 09:50, 11:45

Georgios Styliaris: Coherence-generating power of quantum processes, 14:15, 16:00

Yicheng Zhang: A model of one-dimensional impenetrable SU(N) fermions, 10:05, 11:32

Izhodni podatki

Vrne največje število hkratnih predavanj, torej število potrebnih predavalnic.

Komentar

Za preverjanje rešitev je nalogi priložena datoteka predavanja.txt, ki se bo zgenerirala, ko boš zagnal svoj program.

Uradna rešitev

def stevilo_predavalnic(datoteka):
    """Izračuna število predavalnic, ki jih potrebujemo. Vhodni podatek je datoteka,
    v kateri je v vsaki vrstici napisano predavanje, čas začetka in konca predavanja.
    Podatki v vrstici so ločeni z vejico."""
    predavalnice_po_minutah = 1440 * [0]
    # V dnevu je 1440 minut.
    # Vsaka celica pove, koliko predavanj poteka v neki minuti.
    with open(datoteka, 'r') as predavanja:
        for predavanje in predavanja:
            zacetek = re.findall(", (\d\d):(\d\d), \d\d:\d\d", predavanje)[0]
            konec = re.findall("\d\d:\d\d, (\d\d):(\d\d)", predavanje)[0]
            minute_zacetka = int(zacetek[0]) * 60 + int(zacetek[1])
            minute_konca = int(konec[0]) * 60 + int(konec[1])
            while minute_konca > minute_zacetka:
                predavalnice_po_minutah[minute_zacetka] += 1
                minute_zacetka += 1
    return max(predavalnice_po_minutah)

2008.1.3

Darila

1. podnaloga

Na novoletni zabavi so se prisotni obdarovali z darili. Znano je število prisotnih oseb, za vsak par oseb pa vemo tudi, koliko je bilo vredno darilo, ki ga je dala ena oseba drugi.

Naloga

Napisan je program, ki ugotovi, kdo je imel največ dobička (torej pri kom je razlika med skupno vrednostjo prejetih in podarjenih daril največja). Če je enak največji dobiček doseglo več oseb, izpiše tisto, ki ji je dodeljena manjša številka. Pri tem predpostavimo, da že obstaja naslednja funkcija, ki jo lahko pokličemo, da dobimo podatke o darilih:

  def darilo(a, b):...    # Vrne vrednost darila, ki ga je oseba *a* podarila osebi *b*.

Posamezne osebe so oštevilčene s celimi števili od 1 do stOseb.

Vrstice programa so se pomešale. Uredi in zamakni jih, da bo program deloval.

    if inp == 'exit':
    print('Največ dobička, ' + str(najRazlika) + ', ima oseba ' + str(najKdo) + '.')
    inp = input("Število prisotnih: ")
    if najKdo < 0 or razlika > najRazlika:
    break
    stOseb = int(inp)
    razlika += darilo(j, i) - darilo(i, j)
    najKdo = -1
    for j in range(1, stOseb + 1):
    najRazlika = 0
    while True:
    najRazlika = razlika
    for i in range(1, stOseb + 1):
    razlika = 0
    najKdo = i

Vhodni podatki

Število prisotnih oseb.

Izhodni podatki

Izpis osebe z največ dobička in njen izkupiček.

Uradna rešitev

def darilo(a, b):
    """Vrne vrednost darila, ki ga je oseba a podarila osebi b."""
    if a + 9 > b:
        return a + b - 10
    elif a + 5 > b:
        return a + b + 20
    elif a + 2 > b:
        return (a - b) * b
    elif a > b:
        return 2 * a - 3
    elif a == b:
        return 0
    else:
        return b - a

while True:
    inp = input("Število prisotnih: ")
    if inp == 'exit':
        break
    stOseb = int(inp)
    najKdo = -1
    najRazlika = 0
    for i in range(1, stOseb + 1):
        razlika = 0
        for j in range(1, stOseb + 1):
            razlika += darilo(j, i) - darilo(i, j)
        if najKdo < 0 or razlika > najRazlika:
            najKdo = i
            najRazlika = razlika
    print('Največ dobička, ' + str(najRazlika) + ', ima oseba ' + str(najKdo) + '.')

2008.1.4

Elektronska ključavnica

1. podnaloga

V računskem centru nekega inštituta je vhod varovan z elektronsko ključavnico in številčnico. Na številčnici so števke od $0$ do $9$ in tipka "Prekliči". Geslo je neko zaporedje števk.

Vrata je treba odpreti, takoj ko uporabnik vtipka pravilno geslo. Če pritisne na tipko "Prekliči", se vse tisto, kar je natipkal pred tem, ne upošteva. Prav tako naj se po uspešnem odprtju vrat zbiranje gesla začne znova.

Primer

Če je geslo 3119 in

• uporabnik natipka 3119 $\rightarrow$ vrata odpremo
• uporabnik natipka 3118 $\rightarrow$ vrat ne odpremo
• uporabnik natipka 33119 $\rightarrow$ vrat ne odpremo
• uporabnik natipka 13(prekliči)3119 $\rightarrow$ vrata odpremo

Naloga

Uredi vrstice programa, ki v neskončni zanki bere pritisnjene tipke(vsak pritisk na tipko je sporočen samostojno) in odpre vrata, ko je vtipkano pravilno zaporedje.

natipkano = 0
while True:
    inp = input('')
            natipkano += 1
        break
        if geslo[natipkano] != inp:   # uporabnik se je zatipkal
    elif inp == 'preklici':
        natipkano = 0
            natipkano = -1
        # Preverimo, če je naslednja števka prava
            print(odkleni())
        elif natipkano < len(geslo) - 1:
        else:   # uporabnik je napisal celotno geslo, odklenimo vrata
    if inp == 'exit':
            natipkano = 0
    elif natipkano >= 0:

Predpostaviš lahko, da že obstajata naslednji podprogram in spremenljivka:

• geslo = "..."
• def odkleni():...

Vhodni podatki

Števke, ki jih uporabnik piše v standardni vhod, niz preklici, ko želi uporabnik začeti nov vnos in se je pri prejšnjem zmotil, niz exit, ko želimo končati program. Uporabnik na številčnici sicer nima možnosti, da bi vtipkal exit.

Izhodni podatki

Program izpiše true, ko se vrata odklenejo.

Komentar

Rešitev naj deluje za gesla poljubne dolžine.

Uradna rešitev

geslo = '07062'

### koda, ki odklene vrata
def odkleni():
    ##### skrita koda, ki odklene ključavnico #####
    return True

natipkano = 0
while True:
    inp = input('')
    if inp == 'exit':
        break
    elif inp == 'preklici':
        natipkano = 0
    elif natipkano >= 0:
        # Preverimo, če je naslednja števka prava
        if geslo[natipkano] != inp:   # uporabnik se je zatipkal
            natipkano = -1
        elif natipkano < len(geslo) - 1:
            natipkano += 1
        else:   # uporabnik je napisal celotno geslo, odklenimo vrata
            print(odkleni())
            natipkano = 0

2008.1.5

Kdo je izdal skrivnost?

1. podnaloga

Telefonski operaterji zbirajo tako imenovane prometne podatke o telefonskih pogovorih: kdo je koga klical in kdaj. Čeprav pri tem zbiranju še ne gre za prisluškovanje pogovorom, so tudi prometni podatki strogo zasebni podatki, saj se da na njihovi podlagi marsikaj sklepati o klicočih in jih lahko operaterji posredujejo preiskovalnim organom samo na izrecno zahtevo sodišča ob utemeljenem sumu kaznivih dejanj (ko lahko sodišče odredi tudi prisluškovanje imetnikom izbranih telefonsih številk).

Pa recimo, da teh moralnih dilem nimamo. Dobili smo zaporedni seznam prometnih podatkov nekega operaterja o vseh telefonskih klicih v nekem časovnem obdobju. Elementi seznama so pari telefonskih številk, ki sta uspešno vzpostavili telefonsko zvezo (zaradi enostavnosti bomo pri tej nalogi predpostavili, da so vse telefonske številke štirimestne, npr. interne številke nekega podjetja):

('1705', '2312')

('1326', '1705')

('3789', '1230')

('2312', '2372')

('0137', '1705')

in tako dalje. Seznam je lahko zelo dolg, saj se samo v enem dnevu opravi nekaj milijonov telefonskih klicev. Zaradi enostavnosti v seznamu niso napisani časi klicev, vendar je seznam urejen po časovnem zaporedju, torej prvi element seznama je prvi klic v opazovanem časovnem obdobju in tako naprej.

Zanima nas, ali je neka zaupna informacija, ki jo je imel lastnik telefonske številke a, lahko prek telefonskih pogovorov prišla do osebe, ki je lastnik telefonske številke b. Mogoče se je oseba a z b-jem pogovarjala neposredno (potem je odgovor preprost), lahko pa se je a najprej pogovarjal z nekim c, potem je d poklical c-ja in nazadnje je d poklical b-ja. Informacija od a do b bi lahko prišla tudi še po kakšni drugačni poti, npr. tako, da e najprej pokliče a-ja in potem b pokliče e-ja.

Naloga

Premešale so se vrstice funkcije, ki pregleda seznam vzpostavljenih zvez in za dani dve telefonski številki iz seznama, npr. a in b, ugotovi, ali je lastnik telefonske številke b lahko prišel do zaupne informacije, ki jo je imel lastnik številke a. Uredi vrstice, da bo funkcija delovala.

def obvescen(klici, a, b):
    """Ugotovi, če je glede na dano zaporedje klicev informacija
    lahko prišla od osebe a do osebe b."""
    tel_a = int(a)
    tel_b = int(b)
            return True
    obvescenost = [False] * (10 ** len(a))
        klicatelj = int(klic[0])
    for klic in klici:
        prejemnik = int(klic[1])
            obvescenost[klicatelj] = True
        if obvescenost[prejemnik]:
        if obvescenost[klicatelj]:
    obvescenost[tel_a] = True
        if obvescenost[tel_b]:
    return False
            obvescenost[prejemnik] = True

Vhodni podatki

Seznam parov, pri čemer je par sestavljen iz nizov dveh štirimestnih števil, telefonska številka a, telefonska številka b. Telefonske številke so predstavljene z nizi.

Izhodni podatki

Funkcija vrne true, če je b lahko pridobil zaupno informacijo osebe a, sicer vrne false.

Uradna rešitev

def obvescen(klici, a, b):
    """Ugotovi, če je glede na dano zaporedje klicev informacija
    lahko prišla od osebe a do osebe b."""
    tel_a = int(a)
    tel_b = int(b)
    obvescenost = [False] * (10 ** len(a))
    obvescenost[tel_a] = True
    for klic in klici:
        klicatelj = int(klic[0])
        prejemnik = int(klic[1])
        if obvescenost[prejemnik]:
            obvescenost[klicatelj] = True
        if obvescenost[klicatelj]:
            obvescenost[prejemnik] = True
        if obvescenost[tel_b]:
            return True
    return False